package com.LeeCode;

/**
 * 二叉搜索树的范围和
 */

public class Code938 {
    public static void main(String[] args) {
        Integer[] arr = {10, 5, 15, 3, 7, null, 18};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code938().rangeSumBST(root, 7, 15));
    }

    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        int x = root.val;
        if (x < low)
            return rangeSumBST(root.right, low, high);

        if (x > high)
            return rangeSumBST(root.left, low, high);

        return x + rangeSumBST(root.right, low, high) + rangeSumBST(root.left, low, high);
    }

    private int ans = 0;

    public int rangeSumBST1(TreeNode root, int low, int high) {
        dfs(root, low, high);
        return ans;
    }

    private void dfs(TreeNode root, int low, int high) {
        if (root == null) return;
        if (low <= root.val && root.val <= high) {
            ans += root.val;
            dfs(root.left, low, high);
            dfs(root.right, low, high);
        } else if (root.val < low) {
            dfs(root.right, low, high);
        } else {
            dfs(root.left, low, high);
        }
    }


}
